package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 错误写法
 * <p>
 * 为什么用扎气球的思路不行呢, 最后打印k, 但是左右两个子问题有交集, 这个交叉怎么算情况太多
 *
 * @author tzp
 * @since 2020/9/21
 */
public class LC664 implements DynamicProblem {
    public int strangePrinter(String s) {
        if (s == null || s.length() == 0) return 0;
        s = compress(s);
        int[][] state = new int[s.length()][s.length()];
        for (int step = 1; step <= s.length(); step++) {
            for (int i = 0; i < s.length(); i++) {
                int j = i + step - 1;
                if (j >= s.length()) {
                    break;
                }
                if (i == j) {
                    state[i][j] = 1;
                } else if (j == i + 1) {
                    state[i][j] = s.charAt(i) == s.charAt(j) ? 1 : 2;
                } else {
                    int min = Integer.MAX_VALUE;
                    for (int k = i; k <= j; k++) {//k为轴
                        if (k == i) {
                            min = Math.min(min, 1 + state[i + 1][j]);
                        } else if (k == j) {
                            min = Math.min(min, 1 + state[i][j - 1]);
                        } else {
                            if (s.charAt(k - 1) == s.charAt(j)) {
                                if (k - 2 >= i) {
                                    min = Math.min(min, 1 + state[i][k - 2] + state[k + 1][j]);
                                } else {
                                    min = Math.min(min, 1 + state[k + 1][j]);
                                }
                            } else {
                                min = Math.min(min, 1 + state[i][k - 1] + state[k + 1][j]);
                            }
                        }
                    }
                    state[i][j] = min;
                }
            }
        }
        return state[0][s.length() - 1];
    }

    public static String compress(String s) {
        StringBuilder sb = new StringBuilder();
        sb.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != sb.charAt(sb.length() - 1)) {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        System.out.println(compress("aabbddfaasdfff"));
//        System.out.println(new LC664().strangePrinter("aaabbb"));//2
//        System.out.println(new LC664().strangePrinter("aaba"));//2
//        System.out.println(new LC664().strangePrinter("abcbc"));//4
//        System.out.println(new LC664().strangePrinter("abcabc"));//5
//        System.out.println(new LC664().strangePrinter("tbgtgb"));//4
        System.out.println(new LC664().strangePrinter("bgtgb"));//3
    }
}
